/*
834. 树中距离之和
https://leetcode.cn/problems/sum-of-distances-in-tree/description/
困难 2024/12/4
*/

class Solution {
public:
    // 用于存储每个节点的答案（从该节点出发到所有其他节点的距离之和）
    vector<int> nodeDistances;
    // 用于存储每个节点的子树大小
    vector<int> subtreeSizes;
    // 边的邻接表表示
    vector<vector<int>> adjList;
    // 节点总数
    int nodeCount;

    // 第一次深度优先搜索 (DFS)，计算每个节点的子树大小和初始总距离
    void dfs1(int currNode, int parent, int depth) {
        subtreeSizes[currNode] = 1; // 当前节点本身算一个
        for (int neighbor : adjList[currNode]) {
            if (neighbor == parent) continue; // 不回溯到父节点
            dfs1(neighbor, currNode, depth + 1);
            subtreeSizes[currNode] += subtreeSizes[neighbor]; // 累加子树大小
        }
        // 累加当前节点到所有其他节点的距离
        nodeDistances[0] += depth;
    }

    // 第二次深度优先搜索 (DFS)，根据根节点的结果推导出其他节点的答案
    void dfs2(int currNode, int parent) {
        for (int neighbor : adjList[currNode]) {
            if (neighbor == parent) continue; // 不回溯到父节点
            // 计算邻居节点的答案：当前节点的答案加上除邻居子树外的所有节点数减去两倍邻居子树的大小
            nodeDistances[neighbor] = nodeDistances[currNode] + nodeCount - 2 * subtreeSizes[neighbor];
            dfs2(neighbor, currNode); // 递归处理邻居节点
        }
    }

    // 主函数，计算并返回每个节点作为起点时的距离之和
    vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
        this->nodeCount = n;
        nodeDistances.resize(n, 0);
        subtreeSizes.resize(n, 0);
        adjList.resize(n);

        // 构建无向图的邻接表
        for (const auto& edge : edges) {
            adjList[edge[0]].push_back(edge[1]);
            adjList[edge[1]].push_back(edge[0]);
        }

        // 从节点 0 开始进行第一次 DFS，计算初始总距离
        dfs1(0, -1, 0); // -1 表示没有父节点

        // 从节点 0 开始进行第二次 DFS，计算其他节点的答案
        dfs2(0, -1);

        return nodeDistances;
    }
};